package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 基于有序数组的有序符号表
 * put：O(N)
 * get：O(lgN)
 * 
 * @author 付大石
 */
public class BinarySearchST<K extends Comparable<K>, V> {

    public static void main(String[] args) {

        BinarySearchST<Character, Integer> st = new BinarySearchST<Character, Integer>();
        st.put('S', 0);
        st.put('E', 1);
        st.put('A', 2);
        st.put('R', 3);
        st.put('C', 4);
        st.put('H', 5);
        st.put('E', 6);
        st.put('X', 7);
        st.put('A', 8);
        st.put('M', 9);
        st.put('P', 10);
        st.put('L', 11);
        st.put('E', 12);
        st.put('B',1);
        st.put('D',2);
        for (Character item : st.keys('A', 'F')) {
            System.out.println(item + "   " + st.get(item));
        }
    }

    /**
     * 键值对平行数组
     */
    private K[] keyArr;
    private V[] valueArr;

    /**
     * 平行数组的初始大小
     */
    private static final int INIT_CAPACITY = 10;

    /**
     * 键值对个数
     */
    private int size;

    public BinarySearchST() {

        keyArr = (K[]) new Comparable[INIT_CAPACITY];
        valueArr = (V[]) new Object[INIT_CAPACITY];
    }

    public void put(K key, V value) {

        // 参数校验 //
        Objects.requireNonNull(key, "参数key不能为null");
        if (value == null) {
            delete(key);
			return ;
        }
        // 修改平行数组 //
        int i = rank(key);
        if (keyEquals(key, i)) { // 键值对已存在，更新键值对
            valueArr[i] = value;
            return;
        }
        if (size == keyArr.length) {
            resize(keyArr.length * 2);
        }
        for (int j = size; j > i; j--) {
            keyArr[j] = keyArr[j - 1];
            valueArr[j] = valueArr[j - 1];
        }
        keyArr[i] = key;
        valueArr[i] = value;
        size++;
    }

    /**
     * 调整符号表的容量
     * 
     * @param newCapacity
     */
    private void resize(int newCapacity) {

        if (newCapacity < INIT_CAPACITY) { // 防止符号表容量缩减得过小
            return;
        }
        K[] tempKeyArr = (K[]) new Comparable[newCapacity];
        V[] tempValueArr = (V[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            tempKeyArr[i] = keyArr[i];
            tempValueArr[i] = valueArr[i];
        }
        keyArr = tempKeyArr;
        valueArr = tempValueArr;
    }

    public V get(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        int i = rank(key);
        if (keyEquals(key, i)) {
            return valueArr[i];
        }
        return null;
    }

    public void delete(K key) {

        if (isEmpty()) {
            throw new RuntimeException("符号表为空");
        }
        int i = rank(key);
        if (keyEquals(key, i)) { // 键值对存在于符号表中
            for (int j = i; j < size - 1; j++) {
                keyArr[j] = keyArr[j + 1];
                valueArr[j] = valueArr[j + 1];
            }
            size--;
            if (size * 4 <= keyArr.length) {
                resize(keyArr.length / 2);
            }
        }

    }

    /**
     * 比较{@code key}与{@code keyArr[i]}是否相等
     * 
     * @param key
     * @param i
     * @return
     */
    private boolean keyEquals(K key, int i) {
        return i < size && keyArr[i].compareTo(key) == 0;
    }

    public boolean contains(K key) {
        int i = rank(key);
        return keyEquals(key, i);
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public K min() {
        return keyArr[0];
    }

    public K max() {
        return keyArr[size - 1];
    }

    /**
     * 向下取整
     * 
     * @param key
     * @return
     */
    public K floor(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        int i = rank(key);
        if (keyEquals(key, i)) {
            return keyArr[i];
        } else {
            return keyArr[i - 1];
        }
    }

    /**
     * 向上取整
     * 
     * @param key
     * @return
     */
    public K ceiling(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        return keyArr[rank(key)];
    }

    /**
     * 基于二分查找的rank。当key存在于符号表中（符号表的性质保证key不重复），
     * rank()方法返回其下标位置，也就是排名，也就是表中小于它的键的数量；
     * 当key不存在于符号表中时，rank()方法返回表中小于它的建的数量
     * 
     * @param key
     * @return 返回值范围是[0,size]
     */
    public int rank(K key) {

        int low = 0;
        int high = size - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (keyArr[mid].compareTo(key) == 0) {
                return mid;
            } else if (keyArr[mid].compareTo(key) < 0) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public K select(int k) {
        return keyArr[k];
    }

    public void deleteMin() {
        delete(min());
    }

    public void deleteMax() {
        delete(max());
    }

    public int size(K low, K high) {

        int lowRank = rank(low);
        int highRank = rank(high);
        if (!keyEquals(high, highRank)) {
            highRank--;
        }
        return highRank - lowRank + 1;
    }

    public Iterable<K> keys() {
        return keys(min(), max());
    }

    public Iterable<K> keys(K low, K high) {

        int lowRank = rank(low);
        int highRank = rank(high);
        if (!keyEquals(high, highRank)) {
            highRank--;
        }
        List<K> list = new ArrayList<>();
        for (int i = lowRank; i <= highRank; i++) {
            list.add(keyArr[i]);
        }
        return list;
    }
}
